package com.zds.leetcode;

public class q_86 {
    public static void main(String[] args) {
        // 1->4->3->2->5->2
//        ListNode listNode = new ListNode(1, new ListNode(4, new ListNode(3, new ListNode(2, new ListNode(5, new ListNode(2))))));
//        ListNode partition = new q_86().partition(listNode, 3);
//        System.out.println(partition);
        // 1 0
        ListNode listNode = new ListNode(1);
        ListNode partition = new q_86().partition(listNode, 0);
        System.out.println(partition);
    }

    public ListNode partition(ListNode head, int x) {
        // 遍历原始链表生成两条新链表 small 和 big
        // todo 如何处理等于的情况
        // todo 处理 small 和 big 空的情况
        ListNode small = new ListNode(-1), smallCur = small;
        ListNode big = new ListNode(-1), bigCur = big;
        while (head!=null) {
            if (head.val >= x) {
                bigCur.next = new ListNode(head.val);
                bigCur = bigCur.next;
            } else {
                smallCur.next = new ListNode(head.val);
                smallCur = smallCur.next;
            }
            head = head.next;
        }
        // 如果small 为空，直接返回 big
        if (small.next==null) {
            return big.next;
        }
        // 否则，拼接两个链表
        ListNode res = new ListNode(-1);
        res.next = small.next;
        smallCur.next = big.next;
        return res.next;
    }
}
